/**
 * 
 */
package edu.umd.clip.lm.util;

import java.io.Serializable;
import java.util.Arrays;

/**
 * @author Denis Filimonov <den@cs.umd.edu>
 *
 */
public class CompactReadOnlyIntHashSet implements Serializable {
	private static final long serialVersionUID = 1L;
	
	private final int buckets[];
	private final int keys[];
	private final int numBuckets;
	public static final float DEFAULT_LOAD_FACTOR = 4.0f;
	
	public CompactReadOnlyIntHashSet(int data[]) {
		this(data, DEFAULT_LOAD_FACTOR);
	}
	public CompactReadOnlyIntHashSet(int data[], float loadFactor) {
		this.keys = new int[data.length];
		int minBuckets = Math.round(data.length / loadFactor);
		
		if (minBuckets > Integer.highestOneBit(minBuckets)) {
			minBuckets = Integer.highestOneBit(minBuckets) << 1;
		}
		if (minBuckets == 0) minBuckets = 1;
		
		this.numBuckets = minBuckets;
		this.buckets = new int[numBuckets+1];
		int bucketSizes[] = new int[numBuckets+1];
		
		// compute bucket sizes
		for(int item : data) {
			++bucketSizes[index(item)];
		}
		
		int pos = 0;
		for(int bucket=0; bucket<buckets.length; ++bucket) {
			buckets[bucket] = pos;
			pos += bucketSizes[bucket];
		}
		Arrays.fill(bucketSizes, 0);
		
		// populate the keys
		for(int item : data) {
			int bucket = index(item);
			keys[buckets[bucket]+bucketSizes[bucket]] = item;
			++bucketSizes[bucket];
		}
		
		// sort buckets
		for(int bucket=0; bucket<numBuckets; ++bucket) {
			int start = buckets[bucket];
			int end = buckets[bucket+1];
			if (end - start > 1) {
				Arrays.sort(keys, start, end);
			}
		}
	}
	
	public boolean containsKey(int key) {
		return getKeyPosition(key) >= 0;
	}
	
	final int getKeyPosition(int key) {
		int bucket = index(key);
		int start = buckets[bucket];
		int end = buckets[bucket+1];
		if (end - start < 8) {
			for(int idx=start; idx<end; ++idx) {
				if (keys[idx] == key) return idx;
			}
			return -1;
		} else {
			int idx = Arrays.binarySearch(keys, start, end, key);
			if (idx < 0) return -1;
			return idx;
		}
	}
	
	final int index(int key) {
		int result = key;
		
        result ^= (result >>> 20) ^ (result >>> 12);
        result ^= (result >>> 7) ^ (result >>> 4);

		return result & (numBuckets - 1);
	}

	public final int[] toArray() {
		return keys;
	}
	
	public final int size() {
		return keys.length;
	}
}
